package zcw.com.lib_leet_code;

import zcw.com.lib_leet_code.bean.ListNode;
import zcw.com.lib_leet_code.util.Util;

/**
 * Created by 朱城委 on 2022/1/17.<br><br>
 *
 * 中等：重排链表
 */
public class Topic143 {

    public static void main(String[] args) {
        Topic143 instance = new Topic143();

        int[] array = new int[] {1, 2, 3, 4};
        ListNode head = Util.createList(array);
        instance.reorderList(head);
        Util.printList(head);

        array = new int[] {1, 2, 3, 4, 5};
        head = Util.createList(array);
        instance.reorderList(head);
        Util.printList(head);

        array = new int[] {1, 2};
        head = Util.createList(array);
        instance.reorderList(head);
        Util.printList(head);
    }

    public void reorderList(ListNode head) {
        if(head == null || head.next == null) {
            return ;
        }

        ListNode slow = head;
        ListNode fast = head.next;

        // 利用快慢指针寻找中间的前一个
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        // 把中间节点next置为null
        ListNode end = slow;
        slow = slow.next;
        end.next = null;

        // 反转后半段链表
        ListNode newHead = reverseList(slow);

        // 合并链表
        while (head != null && newHead != null) {
            ListNode temp = newHead;
            newHead = newHead.next;

            temp.next = head.next;
            head.next = temp;
            head = head.next.next;
        }
    }

    private ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }

        ListNode newHead = null;
        while (head != null) {
            ListNode temp = head;
            head = head.next;

            temp.next = newHead;
            newHead = temp;
        }

        return newHead;
    }
}
